package main

import "fmt"

/*
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/genw3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func dailyTemperatures(temperatures []int) []int {
	var stack []int
	res := make([]int, len(temperatures))
	for i, t := range temperatures {
		if len(stack) == 0 {
			stack = append(stack, i)
			continue
		}
		for len(stack) > 0 {
			// 如果准备入栈的数据<= 栈顶，栈顶不需要出栈，直接压栈
			if t <= temperatures[stack[len(stack)-1]] {
				break
			}
			// 如果准备入栈数据>栈顶，不断出栈直到栈顶<= 准备入栈的数据
			topIdx := stack[len(stack)-1]
			res[topIdx] = i - topIdx
			stack = stack[:len(stack)-1] // 栈顶出栈的时候，index差值就是符合要求的数据，最后压栈
		}
		stack = append(stack, i)
	}
	return res
}

func main() {
	temperatures := []int{73, 74, 75, 71, 69, 72, 76, 73}
	fmt.Println(dailyTemperatures(temperatures))
}
